Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory

摘要

Von Neumann's Min-Max Theorem guarantees that each player of a zero-summatrix game has an optimal mixed strategy. This paper gives an elementary proofthat each player has a near-optimal mixed strategy that chooses uniformly atrandom from a multiset of pure strategies of size logarithmic in the number ofpure strategies available to the opponent. For exponentially large games, for which even representing an optimal mixedstrategy can require exponential space, it follows that there are near-optimal,linear-size strategies. These strategies are easy to play and serve as smallwitnesses to the approximate value of the game. As a corollary, it follows that every language has small ``hard'' multisetsof inputs certifying that small circuits can't decide the language. Forexample, if SAT does not have polynomial-size circuits, then, for each n and c,there is a set of n^(O(c)) Boolean formulae of size n such that no circuit ofsize n^c (or algorithm running in time n^c) classifies more than two-thirds ofthe formulae succesfully.